<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>高级排序</title>
</head>
<body>
    <script>
        // 高级排序
        function AdvancedArrayList (){
            this.advancedArray = []
            AdvancedArrayList.prototype.insert = function (item){
                this.advancedArray.push(item)
            }
            AdvancedArrayList.prototype.toString = function (){
                return this.advancedArray.join()
            }
            AdvancedArrayList.prototype.swap = function (m,n){
             var temp = this.advancedArray[m]
             this.advancedArray[m] = this.advancedArray[n]
             this.advancedArray[n] = temp
         }
            // 希尔排序(类似与再二分法)
            AdvancedArrayList.prototype.shellSort = function (){
                // 获取数组的长度
                var length = this.advancedArray.length
                // 根据长度计算增量
                var gap = Math.floor(length/2)
                // 增量不断变小,大于0就继续排序
                while(gap>0){
                    for (let i = gap; i < length; i++) {
                        var j = i
                        var temp = this.advancedArray[i]
                        while(j>gap-1 && this.advancedArray[j-gap]>temp){
                         this.advancedArray[j] = this.advancedArray[j-gap]
                         j -= gap   
                        }
                        // 将选出来的j位置设置为temp
                        this.advancedArray[j] = temp
                    }
                    // 重新计算间隔
                    gap = Math.floor(gap/2)
                }
            }

            // 快速排序(核心思想就是取得一个数然后放到他的指定位置然后分别对左右进行排序)
            AdvancedArrayList.prototype.median = function (left,right){
                // 取出中间位置
                var center = Math.floor((left+right)/2)
                // 判断并且进行交换
                if(this.advancedArray[left]>this.advancedArray[center]){
                    this.swap(left,center)
                }
                if(this.advancedArray[center]>this.advancedArray[right]){
                    this.swap(center,right)
                }
                if(this.advancedArray[left]>this.advancedArray[right]){
                    this.swap(left,right)
                }
                //巧妙的操作:将center移动到right - 1的位置
                this.swap(center,right-1)
                // 返回pivot
                return this.advancedArray[right-1]
            }
            // 快速排序实现
            AdvancedArrayList.prototype.quickSort = function (){
                this.quickSortRec(0,this.advancedArray.length-1)
            }
            AdvancedArrayList.prototype.quickSortRec = function (left, right){
                // 递归结束条件
                if(left >= right)return
                // 获取枢纽
                var pivot = this.median(left,right)
                // 开始交换
                // 记录左边开始位置和右边开始位置
                var i = left
                var j = right - 1
                // 循环查找位置
                while(true){
                    // 遍历所有的值把里面的值大于pivot的值放在pivot右边
                    // 小于pivot放在的左边
                    while (this.advancedArray[++i] < pivot){}
                    while(this.advancedArray[--j] > pivot){}
                    // 当i小于j并找到了不该在左边的值以及右边的值的位置让这两个位置进行交换
                    if(i < j){
                        // 交换两个值
                        this.swap(i,j)
                    }else{
                        // 当i > j时就代表我们遍历越过中位数遍历了直接退出循环就行了
                        break
                    }
                }
                // 3.将枢纽放在正确的位置
                this.swap(i, right - 1)
                // 4.递归枢纽的左右两边让左右两边产生枢纽直到左边等于右边
                // 也就是遍历左边时left小于i-1 遍历右边时i+1大于于right
                this.quickSortRec(left, i - 1)
                this.quickSortRec(i + 1, right)
            }
        } 
         // 初始化数据项
         var list = new AdvancedArrayList()
         list.insert(3)
         list.insert(6)
         list.insert(4)
         list.insert(2)
         list.insert(11)
         list.insert(10)
         list.insert(5)
         // 测试希尔排序
         list.shellSort()
         alert("希尔排序"+list);
         var list2 = new AdvancedArrayList()
         list2.insert(3)
         list2.insert(6)
         list2.insert(4)
         list2.insert(2)
         list2.insert(11)
         list2.insert(10)
         list2.insert(5)
         // 测试中位数选取
         // 原来的数组: 3,6,4,2,11,10,5
         var pivot = list2.median(1, 6) // left:6 right:5 center:2
         alert(pivot) // pivot:5
         alert(list2) // 3,2,4,10,11,5,6
         // 快排
         var list3 = new AdvancedArrayList()
         list3.insert(3)
         list3.insert(6)
         list3.insert(4)
         list3.insert(2)
         list3.insert(11)
         list3.insert(10)
         console.time(1);
         list3.insert(5)
         console.timeEnd(1)
         // 测试快速排序
         list3.quickSort()
         alert("快排:"+list3);
    </script>
</body>
</html>